Sân bay được xây dựng từ năm 1952 đến năm 1955, và mở cửa vào ngày 20 tháng 8 năm 1955 bởi Bộ trưởng Thuộc địa, Alan Lennox-Boyd.[3] Kiến trúc sư của dự án là J. J. Bryan, một kỹ sư công trình công cộng đã có kinh nghiệm xây dựng sân bay tại Malaya và Ấn Độ.[4]

Đây là trụ sở hoạt động của Malayan Airways vào thời điểm này (cùng với sân bay ở Kuala Lumpur), và hãng hàng không này đã có chuyến bay đầu tiên ra khỏi Đông Nam Á năm 1958, sử dụng một chiếc DC-4 thuê từ hãng Qantas, hành trình bay đến Hồng Kông. Động cơ cánh quạt Turbin được hãng sử dụng trong vài năm sau đó, và tên của hãng đã được thay đổi thành Malaysia Airways. Năm 1962, một dịch vụ kiểm soát không lưu dân dụng chung của RAF/Singapore được thành lập để phục vụ cho Bộ Quốc phòng. Trong thời gian đó máy bay dòng Britannia của hãng Bristish Eagle cung cấp phương tiện chuyên chở cho quân đội Anh.

Năm 1966, công ty tập trung nhiều hơn vào Singapore, sau khi mua thêm các máy bay dòng Boeing 707s, mở trụ sở chính tại Singapore, công ty đổi tên thành Malaysia-Singapore Airlines - với một logo sơn màu vàng huỳnh quang nổi bật. Trung tâm hoạt động chính của nó chuyển sang sân bay Paya Lebar, và bắt đầu cung cấp nhiều chuyến bay tiếp cận sâu hơn vào vùng Bắc Á.

Từ năm 1979 đến năm 1980, British Airways, kết hợp với hãng hàng không Singapore, bắt cung cấp các chuyến bay sử dụng máy bay siêu thanh Concorde từ sân bay Heathrow của London đến sân bay Paya Lebar của Singapore.

Hãng Malaysia-Singapore Airlines bị giải thể vào năm 1972; Malaysia Airlines và Singapore Airlines được thành lập – hai hãng này thừa hưởng các máy bay Boeing 707s đã mua trước đó; và Singapore Airlines vẫn có trụ sở ở Paya Lebar. Số lượng hành khách tăng từ 1,7 triệu lên 4 triệu trong khoảng từ năm 1970 đến năm 1975. Sân bay Paya Lebar bị hạn chế hoạt động và mở rộng bởi sự phát triển của các khu bất động sản xung quanh nên Singapore đã bắt đầu việc xây dựng mới sân bay quốc tế Singapore tại Changi năm 1975 và đã đi vào hoạt động vào năm 1981. Paya Lebar sau đó đã ngưng phục vụ các chuyến bay thương mại và dân sự, và sân bay mới Changi đã sử dùng mã IATA (SIN) của Paya Lebar.